﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DataStructures
{
	public abstract class BaseEnumerable<Element, Tree, TreeList, Item> : IBaseEnumerable<Element, Tree, TreeList, Item>
		where Tree : IBaseTree<Element, Tree, TreeList>
		where TreeList : IBaseTreeList<Element, Tree, TreeList>
	{
		#region ctors
		public BaseEnumerable(Tree parent) { _Parent = parent; }
		#endregion ctors


		#region methods

		public void Traverse(ITreeVisitor<Tree> visitor)
		{
			Traverse(_Parent.TraversalType, visitor);
		}
		public void Traverse(TraversalType type, ITreeVisitor<Tree> visitor)
		{
			switch (type)
			{
				case TraversalType.TopDownLeftToRight: TopDownLeftToRight(visitor); break;
				case TraversalType.TopDownRightToLeft: TopDownRightToLeft(visitor); break;
				case TraversalType.BottomUpLeftToRight: BottomUpLeftToRight(visitor); break;
				case TraversalType.BottomUpRightToLeft: BottomUpRightToLeft(visitor); break;
				case TraversalType.PreOrder: PreOrder(visitor); break;
				case TraversalType.PostOrder: PostOrder(visitor); break;
			}
		}
		private void TopDownLeftToRight(ITreeVisitor<Tree> visitor)
		{
			Queue<Tree> tdlr = new Queue<Tree>();
			tdlr.Enqueue(_Parent);
			while (tdlr.Count > 0)
			{
				Tree tree = tdlr.Dequeue();
				visitor.Visit(tree);
				if (tree.HasChildren)
				{
					foreach (Tree child in tree.Children)
						tdlr.Enqueue(child);
				}
			}
		}
		private void TopDownRightToLeft(ITreeVisitor<Tree> visitor)
		{
			Stack<Tree> tdrl = new Stack<Tree>();
			tdrl.Push(_Parent);
			while (tdrl.Count > 0)
			{
				Tree tree = tdrl.Pop();
				visitor.Visit(tree);
				if (tree.HasChildren)
				{
					foreach (Tree child in tree.Children)
						tdrl.Push(child);
				}
			}
		}
		private void BottomUpLeftToRight(ITreeVisitor<Tree> visitor)
		{
			Stack<Tree> tdrl = new Stack<Tree>();
			Stack<Tree> bulr = new Stack<Tree>();
			tdrl.Push(_Parent);
			while (tdrl.Count > 0)
			{
				Tree tree = tdrl.Pop();
				bulr.Push(tree);
				if (tree.HasChildren)
				{
					foreach (Tree child in tree.Children)
						tdrl.Push(child);
				}
			}
			while (bulr.Count > 0)
				visitor.Visit(bulr.Pop());
		}
		private void BottomUpRightToLeft(ITreeVisitor<Tree> visitor)
		{
			Queue<Tree> tdlr = new Queue<Tree>();
			Stack<Tree> burl = new Stack<Tree>();
			tdlr.Enqueue(_Parent);
			while (tdlr.Count > 0)
			{
				Tree tree = tdlr.Dequeue();
				burl.Push(tree);
				if (tree.HasChildren)
				{
					foreach (Tree child in tree.Children)
						tdlr.Enqueue(child);
				}
			}
			while (burl.Count > 0)
				visitor.Visit(burl.Pop());
		}
		private void PreOrder(ITreeVisitor<Tree> visitor)
		{
			Stack<Tree> pre = new Stack<Tree>();
			pre.Push(_Parent);
			Tree current;
			while (pre.Count > 0)
			{
				current = pre.Pop();
				visitor.Visit(current);
				if (current.HasChildren)
				{
					foreach (Tree child in current.Children)
						pre.Push(child);
				}
			}
		}
		private void PostOrder(ITreeVisitor<Tree> visitor)
		{
			Stack<Tree> post = new Stack<Tree>();
			post.Push(_Parent);
			Tree current;
			while (post.Count > 0)
			{
				current = post.Pop();				
				if (current.HasChildren)
				{
					foreach (Tree child in current.Children)
						post.Push(child);
				}
				visitor.Visit(current);
			}
		}
		public Item[] ToArray() { return ToArray(_Parent.TraversalType); }
		public abstract Item[] ToArray(TraversalType type);
		public IEnumerator<Item> GetEnumerator(TraversalType type)
		{
			return new Enumerator<Item>(ToArray(type));
		}
		public IEnumerator<Item> GetEnumerator()
		{
			return GetEnumerator(_Parent.TraversalType);
		}
		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
		{
			throw new NotImplementedException();
		}
		#endregion methods

		#region fields
		private Tree _Parent;
		#endregion fields
	}
}
